package com.imooc.distributedemo.resume.arith;

public class QuickSortSolution {

    public static void main(String[] args) {
        int[] array = {5,2,13,1};//{11,4,2,32,8,99,6,83,44,18,27,228,54};
        int[] sortedArray = quickSort(array);
        System.out.println(sortedArray);
        System.out.println("===============");
        int[] popArray = {11,4,2,32,8,99,6,83,44,18,27,228,54};
        int[] sortedPopArray = popSort(popArray);
        System.out.println(sortedPopArray);
    }

    private static int[] popSort(int[] popArray) {
        for (int i = popArray.length-1; i >=0 ; i--) {
            for (int j = 0; j < i; j++) {
                if(popArray[j]>popArray[j+1]){
                    swap(popArray,j,j+1);
                }
            }
        }
        return popArray;
    }

    /**
     * 选择排序  每一轮选择最小的元素交换到未排定部分的开头
     * @param array
     * @return
     */
    private static int[] quickSort(int[] array) {
        int len = array.length;
        // 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
        for (int i = 0; i < len-1; i++) {
            // 选择区间[i,len-1]里最小元素的索引，交换到下标i
            int minIndex = i;
            for (int j = i+1; j < len; j++) {
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
        return array;
    }

    private static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}
